package 第七周;

/*
 * @author  YxinMiracle
 * @date  2022-05-06 10:17
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.Arrays;

public class 买卖股票的最佳时机4 {

    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[] newPrices = new int[n + 1];
        newPrices[0] = 0;
        for (int i = 1; i <= n; i++) newPrices[i] = prices[i - 1];

        // 初始化状态数组
        // 天 买卖 第几次交易
        int[][][] f = new int[n + 1][2][k + 1];
        Arrays.fill(f[0][0],-1000000000);
        Arrays.fill(f[0][1],-1000000000);
        f[0][0][0] = 0;

        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 2; j++)
                for (int l = 0; l <= k; l++) {
                    // 什么都不做
                    f[i][j][l] = f[i - 1][j][l];
                    if (j == 0) f[i][0][l] = Math.max(f[i][0][l], f[i - 1][1][l] + newPrices[i]); // 卖掉
                    if (j == 1 && l > 0) f[i][1][l] = Math.max(f[i][1][l], f[i - 1][0][l - 1] - newPrices[i]); // 买股票
                }

        int max = 0;
        for (int i = 0; i <= k; i++) max = Math.max(max, f[n][0][i]);
        return max;
    }
}
